1487F - Ones - CodeForces Solution

import time
start = time.time()

N = 51
V = [int("1" * i) if i > 0 else 0 for i in range(N + 1)]
base = [set() for i in range(N + 1)]
base[0].add(0)
vis = {0 : 0}
for i in range(1, 30):
	for j in range(i):
		for k in base[j]:
			for v in [k + V[i - j], abs(k - V[i - j])]:
				if v not in vis:
					base[i].add(v)
					vis[v] = i

s = input()
n = int(s)
ans = sum(((len(s) - i) + (len(s) - i - 1)) * int(s[i]) for i in range(len(s)))
def solve(x, steps):
	global ans
	x = abs(x)
	if time.time() - start > 2.9:
		print(ans)
		exit(0)
	if x in vis:
		ans = min(ans, steps + vis[x])
		return
	for i in range(50, 1, -1):
		if V[i] <= x:
			if steps + i >= ans:
				return
			
			y, stp = x, steps
			while y >= V[i]:
				y -= V[i]
				stp += i
			p1 = (y, stp)

			y, stp = abs(x - V[i + 1]), steps + i + 1
			cnt = 0
			while y >= V[i]:
				y -= V[i]
				stp += i
				cnt += 1
				if cnt > 4:
					solve(*p1)
					return

			p2 = (y, stp)
			if p1[1] > p2[1]:
				p1, p2 = p2, p1
			solve(*p1)
			solve(*p2)
			return
solve(n, 0)

print(ans)
exit(0)